package bTree.LeetCode;

import java.util.HashMap;

public class 被围绕的区域 {
    int [][]dir=new int[][]{{0,1},{-1,0},{0,-1},{1,0}};
    public void solve(char[][] board) {
        int m=board.length,n=board[0].length;
        boolean [][]visited=new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for(int j=0;j<n;j++){
               if(board[i][j]=='O'&&(i==0||i==m-1||j==0||j==n-1)&&!visited[i][j]){
                   dfs(i,j,board,visited);
               }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int i1 = 0; i1 < n; i1++) {
                if(board[i][i1]=='O'){
                    board[i][i1]='X';
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int i1 = 0; i1 < n; i1++) {
                if(board[i][i1]=='!'){
                    board[i][i1]='O';
                }
            }
        }

    }

    private void dfs(int i, int j, char[][] board, boolean[][] visited) {
        board[i][j]='!';
        visited[i][j]=true;
        for (int i1 = 0; i1 < 4; i1++) {
            int nextX=i+dir[i1][0];
            int nextY=j+dir[i1][1];
            if(nextX<0||nextX>=board.length||nextY<0||nextY>=board[0].length||board[nextX][nextY]=='X'||visited[nextX][nextY]){
                continue;
            }
            dfs(nextX,nextY,board,visited);
        }
    }


}